package cn.zzf.algs.note.base.collection.v2;

import java.util.Iterator;
/**
 * 使用动态数组实现的队列
 * @author GaoFeng2017
 * @date 2020/6/15 9:15
 */
public class ResizingArrayQueue<T> implements Iterable<T> {

    /** 元素数组 */
    private Object[] elements = {};

    /** 当前队列元素数量 */
    private int size = 0;

    public ResizingArrayQueue(int initialCapacity) {
        this.init(initialCapacity);
    }

    public ResizingArrayQueue() {
    }

    /** 初始化元素数组 */
    private void init(int initialCapacity) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException();
        }

        this.elements = new Object[initialCapacity];
    }

    /** 将一个元素添加到队尾 */
    public void enqueue(T element) {

        if (this.size == this.elements.length) {
            this.resize(Math.max(this.elements.length, 1) << 1);
        }

        this.elements[this.size++] = element;

    }



    /** 弹出队首元素 */
    @SuppressWarnings("unchecked")
    public T dequeue() {

        if (this.elements.length == 0) {
            return null;
        }

        // 为什么是1/4时，减一半容量，因为小于1/4，说明有3/4的长度的空闲空间，缩减一半，就是去除2/4（1/2）长度的空闲空间，
        // 此时，还剩余一倍size的空闲空间，在下次扩容前，还可以进行多次push()和pop()，当然也可以考虑下只删除后续不添加的场景。
        // 如果缩减到size长度，就偏向于扩容
        // 如果缩减小于1/2就偏向于缩减
        // 所以为了push和pop的次数是公平的，就得缩减1/2
        if (this.size == this.elements.length / 4) {
            this.resize(this.elements.length >> 1);
        }

        T element = (T) this.elements[0];

        for (int i = 0; i < this.size; i++) {
            this.elements[i] = this.elements[i+1];
        }

        this.size--;

        return element;

    }


    private void resize(int length) {
        System.out.println("resizing element array, length is " + length);
        Object[] oldElements = this.elements;
        this.elements = new Object[length];
        for (int i = 0; i < this.size; i++) {
            this.elements[i] = oldElements[i];
        }
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {

            /** 当前迭代到的元素下标 */
            private int currentIndex = 0;

            @Override
            public boolean hasNext() {
                return currentIndex == size;
            }


            @SuppressWarnings("unchecked")
            @Override
            public T next() {
                if (currentIndex == size) {
                    return null;
                }
                return (T) elements[currentIndex++];
            }
        };
    }

}
